/**
 * 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 1->2->3->4->5->NULL, k = 2
 * 输出: 4->5->1->2->3->NULL
 * 解释:
 * 向右旋转 1 步: 5->1->2->3->4->NULL
 * 向右旋转 2 步: 4->5->1->2->3->NULL
 * 示例 2:
 * <p>
 * 输入: 0->1->2->NULL, k = 4
 * 输出: 2->0->1->NULL
 * 解释:
 * 向右旋转 1 步: 2->0->1->NULL
 * 向右旋转 2 步: 1->2->0->NULL
 * 向右旋转 3 步: 0->1->2->NULL
 * 向右旋转 4 步: 2->0->1->NULL
 */
class Solution {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        System.out.println(rotateRight(node1, 101).val);
    }

    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        // 遍历列表，获取总长度
        ListNode node = head;
        int len = 1;
        for (; node.next != null; len++, node = node.next) {
        }
        // 从第s个暂存到末尾
        int s = len - k % len;
        if (s == len) {
            return head;
        }
        int[] tmp = new int[s];
        node = head;
        for (int i = 0; i < s; i++) {
            tmp[i] = node.val;
            node = node.next;
        }
        ListNode startNode = node;
        node = head;
        while (true) {
            node.val = startNode.val;
            if (startNode.next == null) {
                for (int i = 0; i < s; i++) {
                    node = node.next;
                    node.val = tmp[i];
                }
                break;
            }
            node = node.next;
            startNode = startNode.next;
        }
        return head;
    }

    public static ListNode rotateRight2(ListNode head, int k) {
        // 遍历列表，获取总长度和开始的位置
        ListNode node = head;
        ListNode startNode;
        int len = 0;
        int start = 0;
        for (int i = 1; i <= k; i++, start++) {
            if (node.next != null) {
                node = node.next;
            } else {
                len = i;
                start -= len;
                // 尝试去缩小k的值
                k = k % len + len;
                node = head;
            }
        }
        if (start == 0) {
            return head;
        }
        startNode = node;
        // 暂存最后的start个的数据
        int[] tmp = new int[start];
        node = head;
        for (int i = 0; i < start; i++) {
            tmp[i] = node.val;
            node = node.next;
        }
        // 从startNode开始移动，移动到后面为空之后用暂存去补
        node = head;
        while (true) {
            node.val = startNode.val;
            if (startNode.next == null) {
                for (int i = 0; i < start; i++) {
                    node = node.next;
                    node.val = tmp[i];
                }
                break;
            } else {
                node = node.next;
                startNode = startNode.next;
            }
        }
        return head;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}